package org.hhchat.others.ali.p2018;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created this one by huminghao on 2018/3/24.
 */
public class SaleInBatch {


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(), M = in.nextInt();
        List<Integer> target = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            target.add(in.nextInt());
        }
        List<List<Integer>> combinations = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            List<Integer> sub = new ArrayList<>();
            for (int j = 0; j < N; j++) {
                sub.add(in.nextInt());
            }
            combinations.add(sub);
        }

    }

    public static Element dfs(List<List<Integer>> combinations, int end, List<Integer> target) {
        if (end == -1) {
            return new Element(target, combinations.size());
        }else{
            if (isAcceptable(combinations, end, target)) {
                List<Integer> temp = new ArrayList<>(target);
                for(int i = 0; i< target.size();i++) {
                    temp.set(i, temp.get(i) - combinations.get(end).get(i));
                }
                Element res1 = dfs(combinations, end, temp);
                res1.add(end);
                Element res2 = dfs(combinations, end - 1, temp);
                if(res1.compareTo(res2) > 0){
                    return res1;
                }
                return res2;
            }else{
                return dfs(combinations, end - 1, target);
            }
        }

    }


    private static boolean isAcceptable(List<List<Integer>> combinations, int end, List<Integer> target) {
        for(int i = 0 ; i<target.size();i++) {
            if(combinations.get(end).get(i) > target.get(i)) {
                return false;
            }
        }
        return true;
    }


    public static class Element implements Comparable<Element> {
        int[] goods;
        int[] combs;
        int goodKinds;
        int combKinds;
        int sum;

        public Element(List<Integer> target, int combKinds) {
            this.goods = new int[target.size()];
            for (int i = 0; i < target.size(); i++) {
                goods[i] = target.get(i);
                if (goods[i] != 0) {
                    this.goodKinds++;
                }
            }
            this.combs = new int[combKinds];
            this.combKinds = 0;
            this.sum = 0;
        }

        public void add(int index) {
            if (this.combs[index] == 0) {
                this.combKinds++;
            }
            this.combs[index]++;
            this.sum += 1;
        }

        @Override
        public int compareTo(Element o) {
            if (sum == o.sum) {
                if (this.goodKinds == o.goodKinds) {
                    return o.combKinds - this.combKinds;
                } else{
                    return o.goodKinds - this.goodKinds;
                }
            }else{
                return this.sum - o.sum;
            }
        }


    }

}
